const nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3;

//维护一个单调递减的队列
// []

// var maxSlidingWindow =function(nums, k){
//     const len =nums.length;
//     let left =0
//     let right =k -1
//     const res =[]
//     while(right <len){
//         // 获取left 到 right 之间的最大值
//         const max =getMax(nums,left,right)
//         res.push(max)
//         left++
//         right++
//     }
//     return res
// }

// function getMax(nums,left,right) {
//     let max =-Infinity;
//     for(let i =left; i<=right;i++){
//         if(nums[i]>max){
//             max=nums[i]
//         }
//     }
//     return max
// }
var maxSlidingWindow = function (nums, k) {
    const len = nums.length;
    const res = []
    const deque =[] //单调递减队列

    for(let i =0;i<len;i++){
        //不断地将比当前元素小的元素出队
        while(deque.length && nums[i]>nums[deque[deque.length - 1]]){
            deque.pop()
        }
        deque.push(i)
        //当队头元素的索引已经被排除在滑动窗口之外时
        if(deque[0]<=i-k){
            deque.shift()
        }

        //某个时候开始要求最大值
        if(i>=k -1){
            res.push(nums[deque[0]])
        }
    }
    return res
}
console.log(maxSlidingWindow(nums,k));
